package merge;

import java.util.Random;
import java.util.Arrays;

/**
 * @ClassName MergeSort
 * @Description 归并排序
 * @Author ZJX
 * @Date 2024/9/10 15:36
 * @Version 1.0
 */
public class MergeSort {
    public static void mergeSort(int[] array){
        mergeSort(array,0, array.length - 1);
        Arrays.sort(array);
    }

    private static void mergeSort(int[] array,int start,int end){
        if (start >= end){
            return ;
        }


        int mid = start + ((end - start) >> 1);

        mergeSort(array, start, mid);
        mergeSort(array, mid + 1, end);

        // 合并两个已排序的子数组
        merge(array, start, mid, end);
    }

    private static void merge(int[] array, int start, int mid, int end) {
//        创建临时数组
        int[] temp = new int[end - start + 1];
        int k = 0; // temp数组的下标

        int s1 = start;
        int e1 = mid ;

        int s2 = mid + 1;
        int e2 = end;

        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] >= array[s2]){
                temp[k++] = array[s2++];
            } else {
                temp[k++] = array[s1++];
            }
        }

//        走出循环说明 左/右数组有一个已经为空

        // 将左边子数组剩余的元素加入临时数组
        while (s1 <= e1) {
            temp[k++] = array[s1++];
        }

        // 将右边子数组剩余的元素加入临时数组
        while (s2 <= e2) {
            temp[k++] = array[s2++];
        }

        // 将合并后的临时数组复制回原数组的对应位置
        System.arraycopy(temp, 0, array, start, temp.length);

    }

    // 测试归并排序并打印时间消耗
    public static void testMergeSort(int[] array, String description) {
        int[] arrayCopy = Arrays.copyOf(array, array.length);  // 保留原数组，防止改变

        long startTime = System.nanoTime();  // 记录开始时间
        mergeSort(arrayCopy, 0, arrayCopy.length - 1);  // 进行排序
        long endTime = System.nanoTime();    // 记录结束时间

        System.out.println(description + " 排序时间: " + (endTime - startTime) / 1000000.0 + " 毫秒");
    }

    // 生成随机数组
    private static int[] generateRandomArray(int size) {
        Random random = new Random();  // 随机数生成器
        int[] array = new int[size];   // 初始化指定大小的数组
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(size);  // 生成随机数填充数组
        }
        return array;
    }

//    非递归实现归并
    public static void nonRecursiveMergeSort(int[] arr){

    }

    public static void main(String[] args) {
        // 生成测试案例
        int[] smallArray = generateRandomArray(100);     // 100 个元素的数组
        int[] mediumArray = generateRandomArray(1000);   // 1000 个元素的数组
        int[] largeArray = generateRandomArray(10000);   // 10000 个元素的数组

        // 对每个数组进行排序并记录时间
        testMergeSort(smallArray, "小数组 (100个元素)");
        testMergeSort(mediumArray, "中等数组 (1000个元素)");
        testMergeSort(largeArray, "大数组 (10000个元素)");
    }

}


